{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Freedom Trail"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRotateSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #自由之路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>电子游戏“辐射4”中，任务 <strong>“通向自由”</strong> 要求玩家到达名为 “<strong>Freedom Trail Ring”</strong> 的金属表盘，并使用表盘拼写特定关键词才能开门。</p>\n",
    "\n",
    "<p>给定一个字符串&nbsp;<code>ring</code>&nbsp;，表示刻在外环上的编码；给定另一个字符串&nbsp;<code>key</code>&nbsp;，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的<strong>最少</strong>步数。</p>\n",
    "\n",
    "<p>最初，<strong>ring&nbsp;</strong>的第一个字符与 <code>12:00</code> 方向对齐。您需要顺时针或逆时针旋转 <code>ring</code> 以使&nbsp;<strong>key&nbsp;</strong>的一个字符在 <code>12:00</code> 方向对齐，然后按下中心按钮，以此逐个拼写完&nbsp;<strong><code>key</code>&nbsp;</strong>中的所有字符。</p>\n",
    "\n",
    "<p>旋转&nbsp;<code>ring</code><strong>&nbsp;</strong>拼出 key 字符&nbsp;<code>key[i]</code><strong>&nbsp;</strong>的阶段中：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>您可以将&nbsp;<strong>ring&nbsp;</strong>顺时针或逆时针旋转&nbsp;<strong>一个位置&nbsp;</strong>，计为1步。旋转的最终目的是将字符串&nbsp;<strong><code>ring</code>&nbsp;</strong>的一个字符与 <code>12:00</code> 方向对齐，并且这个字符必须等于字符&nbsp;<strong><code>key[i]</code> 。</strong></li>\n",
    "\t<li>如果字符&nbsp;<strong><code>key[i]</code>&nbsp;</strong>已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作&nbsp;<strong>1 步</strong>。按完之后，您可以开始拼写&nbsp;<strong>key&nbsp;</strong>的下一个字符（下一阶段）, 直至完成所有拼写。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/22/ring.jpg\" style=\"height: 450px; width: 450px;\" /></p>\n",
    "\n",
    "<center>&nbsp;</center>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> ring = \"godding\", key = \"gd\"\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong>\n",
    " 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 \n",
    " 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring \"godding\" 2步使它变成 \"ddinggo\"。\n",
    " 当然, 我们还需要1步进行拼写。\n",
    " 因此最终的输出是 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> ring = \"godding\", key = \"godding\"\n",
    "<strong>输出:</strong> 13\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ring.length, key.length &lt;= 100</code></li>\n",
    "\t<li><code>ring</code>&nbsp;和&nbsp;<code>key</code>&nbsp;只包含小写英文字母</li>\n",
    "\t<li><strong>保证</strong> 字符串&nbsp;<code>key</code>&nbsp;一定可以由字符串 &nbsp;<code>ring</code>&nbsp;旋转拼出</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [freedom-trail](https://leetcode.cn/problems/freedom-trail/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [freedom-trail](https://leetcode.cn/problems/freedom-trail/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"godding\"\\n\"gd\"', '\"godding\"\\n\"godding\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        keys = key\n",
    "        indicator=[0]\n",
    "        count = [0]\n",
    "        lenth = len(ring)\n",
    "        while keys:\n",
    "            indexes = []\n",
    "            last_indicator = indicator.copy()\n",
    "            last_count = count.copy()\n",
    "            indicator = []\n",
    "            count = []\n",
    "            for i in range(lenth):\n",
    "                if ring[i] == keys[0]:\n",
    "                    indicator.append(i)\n",
    "                    this_count = lenth*len(key)\n",
    "                    for k in range(len(last_indicator)):\n",
    "                        b = abs(last_indicator[k] - i)\n",
    "                        if b > lenth/2:\n",
    "                            b = lenth - b\n",
    "                        if b + last_count[k] < this_count:\n",
    "                            this_count = b + last_count[k]\n",
    "                    count.append(this_count + 1)\n",
    "            keys = keys[1:]\n",
    "        return min(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n = len(ring)\n",
    "        hs = {}\n",
    "        for idx, item in enumerate(ring):\n",
    "            if item in hs:\n",
    "                hs[item].append(idx)\n",
    "            else:\n",
    "                hs[item] = [idx]\n",
    "        # {'o': [0], 'x': [1, 2, 6], 'i': [3, 7], 'j': [4, 5]}\n",
    "\n",
    "        # dp[i]表示旋转ring旋转到ring[i]需要的最少步数\n",
    "        dp = [float('inf')] * n\n",
    "        # 初始化，ring旋转到key[0]，并不是初始化dp[0]哦\n",
    "        # 在这个例子中，key[0]是j，所以初始化的是dp[4]和dp[5]\n",
    "        for q in hs[key[0]]:\n",
    "            dp[q] = min(q, n-q) + 1    # 初始化后dp[4]=5，dp[5]=4\n",
    "        \n",
    "        # 遍历key[1:]\n",
    "        # 现在我们要拼i，也就是，我们要从[4, 5]到[3, 7]，\n",
    "        # 我们要取4->3，5->3两个距离的最小值，作为dp[3]\n",
    "        # 同理，取4->7，5->7两个距离的最小值，作为dp[7]\n",
    "        # 如何得到[4, 5]？————hs[key[i-1]]\n",
    "        # 如何得到[3, 7]？————hs[key[i]]\n",
    "        for i in range(1, len(key)):\n",
    "            if key[i] != key[i-1]:\n",
    "                for start in hs[key[i-1]]:\n",
    "                    for q in hs[key[i]]:\n",
    "                        dp[q] = min(dp[q], min(abs(q-start), n-abs(q-start)) + dp[start] + 1)\n",
    "                    # 这个start已经没用了，dp[start]重置无穷大\n",
    "                    dp[start] = float('inf')\n",
    "            else:\n",
    "                for q in hs[key[i]]:\n",
    "                    dp[q] += 1\n",
    "        return min(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        \"\"\"\n",
    "        ring = \"godding\", key = \"gd\"\n",
    "        - 对 key 中的每个字符 c，尝试 ring 中的每个 c (顺时针 or 逆时针)\n",
    "        - 得到新的 ring，key 字符数 - 1 \n",
    "        - 递归直到 key 全部匹配完\n",
    "\n",
    "        - 实际无需真正旋转 ring, 用指针 p 来指示 12 点的位置即可\n",
    "        - j 表示 key 需要匹配的字符位置\n",
    "        - dfs(p, j) 计算当前状态下转到 key 末尾需要的最少步数\n",
    "        \"\"\"\n",
    "        @cache\n",
    "        def dfs(p, j):\n",
    "            if j == m:\n",
    "                return 0 \n",
    "            \n",
    "            c = key[j]\n",
    "            res = float('inf')\n",
    "            for pos in char2pos[c]:\n",
    "                # 从 p -> pos\n",
    "                # 步数：abs(pos - p)  or n - abs(pos - p)\n",
    "                step = min(abs(pos-p), n - abs(pos-p))\n",
    "                res = min(res, step + 1 + dfs(pos, j+1))\n",
    "            return res \n",
    "\n",
    "        n, m = len(ring), len(key)\n",
    "        char2pos = defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            char2pos[c].append(i)\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            # 计算在ring[i], key[j..]的最少操作数\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            n = len(ring)\n",
    "            res = inf\n",
    "            for k in char_idx[key[j]]:\n",
    "                delta = abs(k - i)\n",
    "                # 选择顺时针还是逆时针\n",
    "                delta = min(delta, n - delta)\n",
    "                # 把指针播到ring[k], 继续输入key[j+1..]\n",
    "                sub = dp(k, j + 1)\n",
    "                res = min(res, 1 + delta + sub)\n",
    "            return res\n",
    "\n",
    "        char_idx = defaultdict(list)\n",
    "        for i, v in enumerate(ring):\n",
    "            char_idx[v].append(i)\n",
    "        print(char_idx)\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        count = [0]\n",
    "        lenRing = len(ring)\n",
    "        lenKey = len(key)\n",
    "        letter_position = {}\n",
    "        for s in ring:\n",
    "            letter_position[s] = []\n",
    "        for s in letter_position.keys():\n",
    "            for i in range(lenRing):\n",
    "                if ring[i] == s:\n",
    "                    letter_position[s].append(i)\n",
    "        \n",
    "        ikey = 0\n",
    "        while ikey < lenKey:\n",
    "            last_indicator = letter_position[key[ikey-1]] if ikey > 0 else [0]\n",
    "            last_count = count.copy()\n",
    "            count = []\n",
    "            for i in letter_position[key[ikey]]:\n",
    "                this_count = lenRing*lenKey\n",
    "                for k in range(len(last_indicator)):\n",
    "                    b = abs(last_indicator[k] - i)\n",
    "                    if b > lenRing/2:\n",
    "                        b = lenRing - b\n",
    "                    if b + last_count[k] < this_count:\n",
    "                        this_count = b + last_count[k]\n",
    "                count.append(this_count + 1)\n",
    "            ikey += 1\n",
    "        return min(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        def distance(a, b):\n",
    "            return min(abs(a - b), len(ring) - abs(a - b))\n",
    "        \n",
    "        m, n = len(ring), len(key)\n",
    "        dp = [[float('inf')] * m for _ in range(n)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            if ring[i] == key[0]:\n",
    "                dp[0][i] = min(i, m - i) + 1\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            for i in range(m):\n",
    "                if ring[i] == key[j]:\n",
    "                    for k in range(m):\n",
    "                        if dp[j - 1][k] != float('inf'):\n",
    "                            dp[j][i] = min(dp[j][i], dp[j - 1][k] + distance(k, i) + 1)\n",
    "        \n",
    "        return min(dp[n - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "        dp = [inf] * m\n",
    "        dp[0] = 0\n",
    "        for c in key:\n",
    "            new_dp = [inf] * m\n",
    "            for i in range(m):\n",
    "                if ring[i] != c:\n",
    "                    continue\n",
    "                for pre_i in range(m):\n",
    "                    if dp[pre_i] == inf:\n",
    "                        continue\n",
    "                    new_dp[i] = min(new_dp[i], dp[pre_i] + (pre_i - i) % m + 1, dp[pre_i] + (i - pre_i) % m + 1)\n",
    "            dp = new_dp\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n = len(ring)\n",
    "        m = len(key)\n",
    "        dp = [[inf]*(n) for _ in range(m)]\n",
    "        pos = [[] for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            pos[ord(ring[i])-ord('a')].append(i)\n",
    "        \n",
    "        for i in pos[ord(key[0])-ord('a')]:\n",
    "            dp[0][i] = min(i, n-i) + 1\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in pos[ord(key[i])-ord('a')]:\n",
    "                for k in pos[ord(key[i-1])-ord('a')]:\n",
    "                    mid = dp[i-1][k] + min(abs(j-k), n-abs(j-k)) + 1\n",
    "                    dp[i][j] = min(mid, dp[i][j])\n",
    "        return min(dp[m-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        #先用一个哈希表存放ring中各个字母的索引\n",
    "        hs = dict()\n",
    "        for i in range(len(ring)):\n",
    "            if ring[i] not in hs:\n",
    "                hs[ring[i]] = [i]\n",
    "            else:\n",
    "                hs[ring[i]].append(i)\n",
    "        \n",
    "        #初始化dp数组，包括初始化第一行\n",
    "        m,n = len(ring),len(key)\n",
    "        # 这个初始化值得思考\n",
    "        dp = [float('inf')]*m\n",
    "        # 第一个位置\n",
    "        for q in hs[key[0]]:\n",
    "            # 更新最近的移动+input一次\n",
    "            dp[q] = min(q,m-q)+1\n",
    "        # print(dp)\n",
    "\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            #分为两种情况：1.正在处理的字母与上一个字母不同；2.正在处理的字母与上一个字母相同；\n",
    "            if key[i]!=key[i-1]:\n",
    "                # 上一个\n",
    "                for p in hs[key[i-1]]:\n",
    "                    # 这一个\n",
    "                    for j in hs[key[i]]:\n",
    "                        dp[j] = min(dp[j],min(abs(j-p),m-abs(j-p))+dp[p]+1)\n",
    "                    dp[p] = float('inf')\n",
    "\n",
    "            else:\n",
    "                for j in hs[key[i]]:\n",
    "                    dp[j]+=1\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        l1 = len(ring)\n",
    "        l2 = len(key)\n",
    "        dp = [[math.inf]*l1 for _ in range(l2)]\n",
    "\n",
    "        for i in range(l1):\n",
    "            if ring[i] == key[0]:\n",
    "                dp[0][i] = 1 + min(i, l1 - i)\n",
    "\n",
    "        for i in range(1, l2):\n",
    "            for j in range(l1):\n",
    "                if ring[j] == key[i]:\n",
    "                    for m in range(l1):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i - 1][m] + 1 + min(abs(j - m), l1 - abs(j - m)))\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n=len(ring)\n",
    "        m=len(key)\n",
    "        dp=[[float('inf')]*n for _ in range(m)]\n",
    "        #lookup 统计key中的各字符出现的位置\n",
    "        lookup=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            lookup[ring[i]].append(i)\n",
    "        #dp 初始化，\n",
    "        for i in lookup[key[0]]:\n",
    "            dp[0][i]=min(i,n-i)+1\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in lookup[key[i]]:#key[i]字符出现的位置\n",
    "                for k in lookup[key[i-1]]:#key[i-1]字符出现的位置\n",
    "                    #t是上一个字符原本位置是k的被移动到了12:00,\n",
    "                    #那么当前字符位置是j的距离k的最短距离是多少\n",
    "                    if j>k:\n",
    "                        t=min(j-k,n-(j-k))\n",
    "                    else:\n",
    "                        t=min(k-j,n-(k-j))\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][k]+1+t)\n",
    "        return min(dp[-1])            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n=len(ring)\n",
    "        m=len(key)\n",
    "        dp=[[float('inf')]*n for _ in range(m)]\n",
    "        #lookup 统计key中的各字符出现的位置\n",
    "        lookup=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            lookup[ring[i]].append(i)\n",
    "        #dp 初始化，\n",
    "        for i in lookup[key[0]]:\n",
    "            dp[0][i]=min(i,n-i)+1\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in lookup[key[i]]:#key[i]字符出现的位置\n",
    "                for k in lookup[key[i-1]]:#key[i-1]字符出现的位置\n",
    "                    #t是上一个字符原本位置是k的被移动到了12:00,\n",
    "                    #当前字符位置是j的距离k的最短距离是t\n",
    "                    if j>k:\n",
    "                        t=min(j-k,n-(j-k))\n",
    "                    else:\n",
    "                        t=min(k-j,n-(k-j))\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][k]+1+t)\n",
    "        return min(dp[-1])            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        lookup = defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            lookup[c].append(i)\n",
    "        q = [(0, 0, 0)]\n",
    "        visited = set()\n",
    "        while q:\n",
    "            steps, ringI, keyI = heapq.heappop(q)\n",
    "            if (ringI, keyI) in visited:\n",
    "                continue\n",
    "            visited.add((ringI, keyI))\n",
    "            if keyI == len(key):\n",
    "                return steps + len(key)\n",
    "            c = key[keyI]\n",
    "            after = bisect_right(lookup[c], ringI)\n",
    "            before = after - 1\n",
    "            after = after % len(lookup[c])\n",
    "            before = (before + len(lookup[c])) % len(lookup[c])\n",
    "            bI, aI = lookup[c][before], lookup[c][after]\n",
    "            heapq.heappush(q, (steps + min(abs(ringI - bI), len(ring) - max(ringI, bI) + min(ringI, bI)), bI, keyI + 1))\n",
    "            if aI != bI:\n",
    "                heapq.heappush(q, (steps + min(abs(aI - ringI), len(ring) - max(ringI, aI) + min(ringI, aI)), aI, keyI + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "        indexDict = defaultdict(list)\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            c = ring[i]\n",
    "            if c not in indexDict:\n",
    "                indexDict[c] = []\n",
    "            indexDict[c].append(i)\n",
    "        return self.helper(ring, key, dp, n, m, indexDict, 0, 0)\n",
    "    \n",
    "    def helper(self, ring, key, dp, n, m, indexDict, i, j):\n",
    "        if j == n:\n",
    "            return 0\n",
    "        if dp[i][j] != 0:\n",
    "            return dp[i][j]\n",
    "        c = key[j]\n",
    "        res = float(\"inf\")\n",
    "        for newI in indexDict[c]:\n",
    "            distance = abs(i - newI)\n",
    "            distance = min(distance, m - distance)\n",
    "            subProblem = self.helper(ring, key, dp, n, m, indexDict, newI, j + 1)\n",
    "            res = min(res, 1 + distance + subProblem)\n",
    "        dp[i][j] = res\n",
    "        return dp[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        dic=collections.defaultdict(list)\n",
    "        for k in key:\n",
    "            if k not in dic:\n",
    "                for i,v in enumerate(ring):\n",
    "                    if v==k:\n",
    "                        dic[k].append(i)\n",
    "\n",
    "        counter=[{0:0}]\n",
    "        \n",
    "        path=collections.defaultdict()\n",
    "\n",
    "        for i in range(len(key)):\n",
    "            counter.append({})\n",
    "            for j in dic[key[i]]:\n",
    "                tmp=[]\n",
    "                for start in counter[i]:\n",
    "                    pred=counter[i][start]\n",
    "                    s=str(start)+\"-\"+str(j)\n",
    "                    \n",
    "                    d1=abs(start-j)\n",
    "                    d2=abs(len(ring)-d1)\n",
    "                    d=min(d1,d2)\n",
    "                        #path[s]=d\n",
    "                    tmp.append(pred+d)\n",
    "                \n",
    "                counter[i+1][j]=min(tmp)+1\n",
    "\n",
    "        return min(counter[-1].values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n=len(ring)\n",
    "        m=len(key)\n",
    "        dp=[[float('inf')]*n for _ in range(m)]\n",
    "        #lookup 统计key中的各字符出现的位置\n",
    "        lookup=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            lookup[ring[i]].append(i)\n",
    "        #dp 初始化，\n",
    "        for i in lookup[key[0]]:\n",
    "            dp[0][i]=min(i,n-i)+1\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in lookup[key[i]]:#key[i]字符出现的位置\n",
    "                for k in lookup[key[i-1]]:#key[i-1]字符出现的位置\n",
    "                    #t计算的是上一个字符原本位置是k的被移动到了12:00,\n",
    "                    #那么当前字符位置是j的距离k的最短距离是多少\n",
    "                    if j>k:\n",
    "                        t=min(j-k,n-(j-k))\n",
    "                    else:\n",
    "                        t=min(k-j,n-(k-j))\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][k]+1+t)\n",
    "        return min(dp[-1])            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        dp = [[99999999 for _ in range(len(ring))] for _ in range(len(key))]\n",
    "        \n",
    "        for i in range(len(ring)):\n",
    "            if key[0] == ring[i]:\n",
    "                dp[0][i] = min(i, len(ring) - i) + 1\n",
    "\n",
    "        for i in range(1, len(key)):\n",
    "            c = key[i]\n",
    "\n",
    "            for j in range(len(ring)):\n",
    "                if ring[j] == key[i - 1]:\n",
    "                    for k in range(len(ring)):\n",
    "                        if ring[k] == key[i]:\n",
    "                            dp[i][k] = min(dp[i][k], 1 + dp[i - 1][j] + min(abs(k - j), len(ring) - abs(k - j)))\n",
    "        \n",
    "        res = 99999999\n",
    "        for i in range(len(ring)):\n",
    "            res = min(res, dp[len(key) - 1][i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n = len(ring)\n",
    "        m = len(key)\n",
    "        ring_dict = collections.defaultdict(list)\n",
    "        for i,char in enumerate(ring):\n",
    "            ring_dict[char].append(i)\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        #dp[i][j]表示key中第i个字符在用ring中第j个字符输入的最小步数\n",
    "        for index in ring_dict[key[0]]:\n",
    "           dp[0][index] = min(index,n - index)\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in ring_dict[key[i]]:\n",
    "                for k in ring_dict[key[i - 1]]:\n",
    "                    step = min(abs(j - k),n - abs(j - k))\n",
    "                    dp[i][j] = min(dp[i][j],dp[i - 1][k] + step)\n",
    "        \n",
    "        return min(dp[-1]) + m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        dp = []\n",
    "        for i in range(len(key)):\n",
    "            dp.append([2 ** 31] * len(ring))\n",
    "        for i in range(len(ring)):\n",
    "            if ring[i] == key[0]:\n",
    "                dp[0][i] = min(i, len(ring) - i) + 1\n",
    "        for i in range(1, len(key)):\n",
    "            p = []\n",
    "            for j in range(len(ring)):\n",
    "                if key[i] == ring[j]:\n",
    "                    p.append(j)\n",
    "            for j in range(len(ring)):\n",
    "                if dp[i - 1][j] != 2 ** 31:\n",
    "                    for positon in p:\n",
    "                        dp[i][positon] = min(dp[i][positon], dp[i - 1][j] + min(abs(j - positon), len(ring) - abs(j - positon)) + 1)\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        #先用一个哈希表存放ring中各个字母的索引\n",
    "        hs = dict()\n",
    "        for i in range(len(ring)):\n",
    "            if ring[i] not in hs:\n",
    "                hs[ring[i]] = [i]\n",
    "            else:\n",
    "                hs[ring[i]].append(i)\n",
    "        \n",
    "        #初始化dp数组，包括初始化第一行\n",
    "        m,n = len(ring),len(key)\n",
    "        # 这个初始化值得思考\n",
    "        dp = [float('inf')]*m\n",
    "        # 第一个位置\n",
    "        for q in hs[key[0]]:\n",
    "            # 更新最近的移动+input一次\n",
    "            dp[q] = min(q,m-q)+1\n",
    "        # print(dp)\n",
    "\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            #分为两种情况：1.正在处理的字母与上一个字母不同；2.正在处理的字母与上一个字母相同；\n",
    "            if key[i]!=key[i-1]:\n",
    "                # 上一个\n",
    "                for p in hs[key[i-1]]:\n",
    "                    # 这一个\n",
    "                    for j in hs[key[i]]:\n",
    "                        dp[j] = min(dp[j],min(abs(j-p),m-abs(j-p))+dp[p]+1)\n",
    "                    # 更新，因为每次只保留更新完后的j\n",
    "                    dp[p] = float('inf')\n",
    "\n",
    "            else:\n",
    "                for j in hs[key[i]]:\n",
    "                    dp[j]+=1\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "        indexDict = defaultdict(list)\n",
    "        dp = [[9999] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            dp[i][n] = 0\n",
    "        for i in range(m):\n",
    "            c = ring[i]\n",
    "            if c not in indexDict:\n",
    "                indexDict[c] = []\n",
    "            indexDict[c].append(i)\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            for i in range(m):\n",
    "                res = float(\"inf\")\n",
    "                indexList = indexDict[key[j]]\n",
    "                for k in indexList:\n",
    "                    delta = abs(i - k)\n",
    "                    delta = min(delta, m - delta)\n",
    "                    res = min(res, 1 + delta + dp[k][j + 1])\n",
    "                dp[i][j] = res\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as d\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "\n",
    "        Choices = d()  # 把每个key对应的可选的ring的字母的index做成字典。\n",
    "        for k in key:\n",
    "            if k in Choices:\n",
    "                continue\n",
    "            else:\n",
    "                Choices[k] = []\n",
    "                for ri, r in enumerate(ring):\n",
    "                    if r == k:\n",
    "                        Choices[k].append(ri)\n",
    "\n",
    "        counter = [{0 : 0}]\n",
    "        Path = d()\n",
    "\n",
    "        for keyi in range(len(key)): # 一共len(key)个格子。\n",
    "            counter.append({})\n",
    "            for choice in Choices[key[keyi]]:  # choice是个index，是表示对于在key上第keyi个字母来说，ring里有哪几个位置的字母可以选择。\n",
    "                temp = []\n",
    "                for start in counter[keyi].keys():  # start表示上一个格子里，有几种情况可以到达当前的choice。\n",
    "                    previous_distance = counter[keyi][start]\n",
    "\n",
    "                    s = str(start) + \"-\" + str(choice)\n",
    "                    if s not in Path:\n",
    "                        d1 = abs(choice - start)\n",
    "                        d2 = abs(len(ring) - d1)\n",
    "                        newc = min(d1, d2)\n",
    "                        Path[s] = newc\n",
    "\n",
    "                    temp.append(previous_distance + Path[s])\n",
    "\n",
    "                counter[keyi + 1][choice] = min(temp) + 1  # 只需要保留最小值  再加1表示按下按钮。\n",
    "\n",
    "        # print(Choices)\n",
    "        final = min(counter[-1].values())\n",
    "\n",
    "        return final\n",
    "        \n",
    "        '''\n",
    "        def scroll(current, target):\n",
    "            targletter = key[target]\n",
    "            ptl = ptr = current\n",
    "            step = 0\n",
    "            while ring[ptl] != targletter and ring[ptr] != targletter:\n",
    "                if ptl == 0 and ptr == len(ring)-1:\n",
    "                    ptl = len(ring)-1\n",
    "                    ptr = 0\n",
    "                elif ptl == 0 and ptr != len(ring)-1:\n",
    "                    ptl = len(ring)-1\n",
    "                    ptr += 1\n",
    "                elif ptl != 0 and ptr == len(ring)-1:\n",
    "                    ptl -= 1\n",
    "                    ptr = 0\n",
    "                else:\n",
    "                    ptl -= 1\n",
    "                    ptr += 1\n",
    "                step += 1\n",
    "            further = target\n",
    "            while key[further] == key[target] and further < len(key)-1:\n",
    "                further += 1\n",
    "            if ptr != ptl and ring[ptr] == targletter and ring[ptl] == targletter:\n",
    "                if target == len(key)-1:\n",
    "                    return [step,ptl]\n",
    "                else:\n",
    "                    howleft = scroll(ptl,further)\n",
    "                    howright = scroll(ptr,further)\n",
    "                    if howleft[0] < howright[0]:\n",
    "                        return [step, ptl]\n",
    "                    else:\n",
    "                        return [step, ptr]\n",
    "            if ring[ptr] == targletter:\n",
    "                return [step,ptr]\n",
    "            elif ring[ptl] == targletter:\n",
    "                return [step,ptl]\n",
    "                \n",
    "\n",
    "        step = len(key)\n",
    "        current = 0\n",
    "        curletter = ring[current]\n",
    "        for target in range(0,len(key)):\n",
    "            howscroll = scroll(current, target)\n",
    "            step += howscroll[0]\n",
    "            current = howscroll[1]\n",
    "            curletter = ring[current]\n",
    "            \n",
    "        return step\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as d\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "\n",
    "        Choices = d()  # 把每个key对应的可选的ring的字母的index做成字典。\n",
    "        for k in key:\n",
    "            if k in Choices:\n",
    "                continue\n",
    "            else:\n",
    "                Choices[k] = []\n",
    "                for ri, r in enumerate(ring):\n",
    "                    if r == k:\n",
    "                        Choices[k].append(ri)\n",
    "\n",
    "        counter = [{0 : 0}]\n",
    "        Path = d()\n",
    "\n",
    "        for keyi in range(len(key)): # 一共len(key)个格子。\n",
    "            counter.append({})\n",
    "            for choice in Choices[key[keyi]]:  # choice是个index，是表示对于在key上第keyi个字母来说，ring里有哪几个位置的字母可以选择。\n",
    "                temp = []\n",
    "                for start in counter[keyi].keys():  # start表示上一个格子里，有几种情况可以到达当前的choice。\n",
    "                    previous_distance = counter[keyi][start]\n",
    "\n",
    "                    s = str(start) + \"-\" + str(choice)\n",
    "                    if s not in Path:\n",
    "                        d1 = abs(choice - start)\n",
    "                        d2 = abs(len(ring) - d1)\n",
    "                        newc = min(d1, d2)\n",
    "                        Path[s] = newc\n",
    "\n",
    "                    temp.append(previous_distance + Path[s])\n",
    "\n",
    "                counter[keyi + 1][choice] = min(temp) + 1  # 只需要保留最小值  再加1表示按下按钮。\n",
    "\n",
    "        # print(Choices)\n",
    "        final = min(counter[-1].values())\n",
    "\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        char2index = {}\n",
    "        for i, c in enumerate(ring):\n",
    "            if c not in char2index:\n",
    "                char2index[c] = [i]\n",
    "            else:\n",
    "                char2index[c].append(i)\n",
    "        memo = [[0 for i in range(len(key))] for j in range(len(ring))]\n",
    "        return self.dp(ring, 0, key, 0, char2index, memo)\n",
    "    \n",
    "    def dp(self, ring, i, key, j, char2index, memo):\n",
    "        if j == len(key):\n",
    "            return 0\n",
    "        if memo[i][j]:\n",
    "            return memo[i][j]\n",
    "        n = len(ring)\n",
    "        res = float(\"inf\")\n",
    "        for k in char2index[key[j]]:\n",
    "            delta = abs(k - i)\n",
    "            delta = min(delta, n - delta)\n",
    "            subProblem = self.dp(ring, k, key, j + 1, char2index, memo)\n",
    "            res = min(res, 1 + delta + subProblem)\n",
    "        memo[i][j] = res\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 【解法一】dp\n",
    "# 【解法二】用dfs（回溯）遍历（穷举）每个位置上的所有选择（例如godding，两个d，分别递归），此外，顺时针逆时针旋转也是两种选择方式\n",
    "# 对于key（目标）中的一个字符（例如d），在ring中找到他对应的所有索引: dfs(i, j): ring对齐i时从key[j]到末尾需要的步数 \n",
    "# 题解：https://leetcode.cn/problems/freedom-trail/solutions/1/python3-lai-ba-zhan-shi-shi-shi-ju-zhuquan-guo-zui/\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "        char_index = collections.defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            char_index[c].append(i)\n",
    "        dp = [[float(\"inf\")] * (n + 1) for _ in range(m)]   # dp有n+1列，原因是需要一列来存储“全拼完”的状态，这个状态下cost是0\n",
    "        # dp[-1][-1] = 0\n",
    "        for i in range(m):  # 注意dp数组的初始化\n",
    "            dp[i][-1] = 0\n",
    "        # for i in range(m):\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            for i in range(m):\n",
    "                for k in char_index[key[j]]:\n",
    "                    step = min(abs(i - k), m - abs(i - k)) + 1  # 注意这里是i不是j，因为要计算的是ring从i转到k需要的步数\n",
    "                    dp[i][j] = min(dp[i][j], dp[k][j + 1] + step)\n",
    "        # print(dp)\n",
    "        return dp[0][0]\n",
    "        \n",
    "        \n",
    "        # n = len(ring)\n",
    "        # m = len(key)\n",
    "        # dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        # char_idx = collections.defaultdict(list)\n",
    "        # for idx, c in enumerate(ring):\n",
    "        #     char_idx[c].append(idx)\n",
    "        # for i in range(n, -1, -1):\n",
    "        #     for j in range(1, m + 1):\n",
    "        #         for idx in char_idx[key[j - 1]]:\n",
    "        #             step = min(abs(idx - i), n - abs(idx - i))\n",
    "        #             dp[i][j] = min(\n",
    "        #                 dp[i][j],\n",
    "        #                 dp[idx][j + 1] + step + 1\n",
    "        #             ) if dp[i][j] != 0 else dp[idx][j + 1] + step + 1\n",
    "        # return dp[0][0]\n",
    "\n",
    "        # for i in range(1, n + 1):\n",
    "        #     if ring[i - 1] == key[-1]:\n",
    "        #         dp[i][-1] = 1\n",
    "        # for i in range(n, -1, -1):\n",
    "        #     for j in range(m, -1, -1):\n",
    "        #         dp[i][j] = min(\n",
    "        #             dp[i][j - 1] + abs(i - ), # 【注意】 这里难以确定上一轮i的索引，解决方案是，使用一个字典记录ring中每个字符的index\n",
    "\n",
    "        #         )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        char_dict = collections.defaultdict(list)\n",
    "        for index, c in enumerate(ring):\n",
    "            char_dict[c].append(index)\n",
    "        \n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "\n",
    "        # d[i][j]: 当指针指向ring[i]时，拼写key[j:]的最小步数\n",
    "        # base case: d[i][n] = 0\n",
    "        d = [[0] * (n + 1) for i in range(m)]\n",
    "\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            for i in range(m):\n",
    "                d[i][j] = float('INF')\n",
    "                for k in char_dict[key[j]]:\n",
    "                    step = min(abs(k - i), abs(m - abs(k - i)))\n",
    "                    d_i_j = d[k][j + 1] + step + 1\n",
    "                    d[i][j] = min(d[i][j], d_i_j)\n",
    "        \n",
    "        return d[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        chartodic = collections.defaultdict(set)\n",
    "        m, n = len(ring), len(key)\n",
    "        dp = [[0] * (n + 1) for _ in range(m)]\n",
    "        for index, char in enumerate(ring):\n",
    "            chartodic[char].add(index)\n",
    "        \n",
    "        for j in range(n-1, -1, -1):\n",
    "            for i in range(m):\n",
    "                for k in chartodic[key[j]]:\n",
    "                    min_dic = min(abs(k - i), m - abs(k - i))\n",
    "                    d_i_j = min_dic + 1 + dp[k][j + 1]\n",
    "                    dp[i][j] = min(dp[i][j], d_i_j) if dp[i][j] else d_i_j\n",
    "        \n",
    "        return dp[0][0]\n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        choice=collections.defaultdict(list)\n",
    "\n",
    "        for k in key:\n",
    "            if k in choice:\n",
    "                continue\n",
    "            else:\n",
    "                for i,r in enumerate(ring):\n",
    "                    if r==k:\n",
    "                        choice[r].append(i)\n",
    "        \n",
    "        counter = [{0 : 0}]\n",
    "\n",
    "        path=collections.defaultdict()\n",
    "\n",
    "        for i in range(len(key)):\n",
    "            counter.append({})\n",
    "            for j in choice[key[i]]:\n",
    "                tmp=[]\n",
    "                for start in counter[i]:\n",
    "                    previous_distance = counter[i][start]\n",
    "                    s=str(start) + \"-\" + str(j)\n",
    "                    if s not in path:\n",
    "                        d1 = abs(j - start)\n",
    "                        d2 = abs(len(ring) - d1)\n",
    "                        newc = min(d1, d2)\n",
    "                        path[s] = newc\n",
    "                    tmp.append(previous_distance + path[s])\n",
    "\n",
    "                counter[i + 1][j] = min(tmp) + 1  # 只需要保留最小值  再加1表示按下按钮。\n",
    "\n",
    "        # print(Choices)\n",
    "        final = min(counter[-1].values())\n",
    "\n",
    "        return final\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as d\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "\n",
    "        Choices = d()  # 把每个key对应的可选的ring的字母的index做成字典。\n",
    "        for k in key:\n",
    "            if k in Choices:\n",
    "                continue\n",
    "            else:\n",
    "                Choices[k] = []\n",
    "                for ri, r in enumerate(ring):\n",
    "                    if r == k:\n",
    "                        Choices[k].append(ri)\n",
    "\n",
    "        counter = [{0 : 0}]\n",
    "        Path = d()\n",
    "\n",
    "        for keyi in range(len(key)): # 一共len(key)个格子。\n",
    "            counter.append({})\n",
    "            for choice in Choices[key[keyi]]:  # choice是个index，是表示对于在key上第keyi个字母来说，ring里有哪几个位置的字母可以选择。\n",
    "                temp = []\n",
    "                for start in counter[keyi].keys():  # start表示上一个格子里，有几种情况可以到达当前的choice。\n",
    "                    previous_distance = counter[keyi][start]\n",
    "\n",
    "                    s = str(start) + \"-\" + str(choice)\n",
    "                    if s not in Path:\n",
    "                        d1 = abs(choice - start)\n",
    "                        d2 = abs(len(ring) - d1)\n",
    "                        newc = min(d1, d2)\n",
    "                        Path[s] = newc\n",
    "\n",
    "                    temp.append(previous_distance + Path[s])\n",
    "\n",
    "                counter[keyi + 1][choice] = min(temp) + 1  # 只需要保留最小值  再加1表示按下按钮。\n",
    "\n",
    "        # print(Choices)\n",
    "        final = min(counter[-1].values())\n",
    "\n",
    "        return final\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        dic=collections.defaultdict(list)\n",
    "        for k in key:\n",
    "            if k not in dic:\n",
    "                for i,v in enumerate(ring):\n",
    "                    if v==k:\n",
    "                        dic[k].append(i)\n",
    "\n",
    "        counter=[{0:0}]\n",
    "        \n",
    "        path=collections.defaultdict()\n",
    "\n",
    "        for i in range(len(key)):\n",
    "            counter.append({})\n",
    "            for j in dic[key[i]]:\n",
    "                tmp=[]\n",
    "                for start in counter[i]:\n",
    "                    pred=counter[i][start]\n",
    "                    s=str(start)+\"-\"+str(j)\n",
    "                    if s not in path:\n",
    "                        d1=abs(start-j)\n",
    "                        d2=abs(len(ring)-d1)\n",
    "                        d=min(d1,d2)\n",
    "                        path[s]=d\n",
    "                    tmp.append(pred+path[s])\n",
    "                \n",
    "                counter[i+1][j]=min(tmp)+1\n",
    "\n",
    "        return min(counter[-1].values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        ring_dict = {}\n",
    "        for idx, i in enumerate(ring):\n",
    "            if i not in ring_dict:\n",
    "                ring_dict[i] = [idx]\n",
    "            else:\n",
    "                ring_dict[i].append(idx)\n",
    "        \n",
    "        dp = [[float(\"inf\") for i in range(len(ring))] for j in range(len(key))]\n",
    "        \n",
    "        s = key[0]\n",
    "        idx_list = ring_dict[s]\n",
    "        for i in idx_list:\n",
    "            dp[0][i] = 1+min(i, len(ring)-i)\n",
    "        for i in range(1, len(key)):\n",
    "            idx_list = ring_dict[key[i]]\n",
    "            for j in idx_list:\n",
    "                for k in range(len(ring)):\n",
    "                    if dp[i-1][k]==float(\"inf\"):\n",
    "                        continue\n",
    "                    dp[i][j] = min(dp[i][j], 1+dp[i-1][k]+min(abs(k-j), len(ring)-abs(k-j)))\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charToIndex = collections.defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            charToIndex[c].append(i)\n",
    "        m, n = len(key), len(ring)\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        for k in charToIndex[key[0]]:\n",
    "            dp[0][k] = min(k, n - k) + 1\n",
    "        for i in range(1, m):\n",
    "            for j in charToIndex[key[i]]:\n",
    "                for k in charToIndex[key[i - 1]]:\n",
    "                    delta = abs(j - k)\n",
    "                    delta = min(delta, n - delta)\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + delta + 1)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m=len(ring)\n",
    "        n=len(key)\n",
    "        dp=[None]*m\n",
    "        for i in range(m):\n",
    "            dp[i]=[0]*n\n",
    "        c2i=dict()\n",
    "        for i,c in enumerate(ring):\n",
    "            c2i.setdefault(c,[]).append(i)\n",
    "        def distance(i, j):\n",
    "            return min(abs(i-j),m-abs(i-j))\n",
    "        for i in range(m):\n",
    "            if ring[i] != key[0]:\n",
    "                dp[i][0]= float('inf')\n",
    "            dp[i][0] = distance(0, i) + 1\n",
    "        for j in range(1, n):\n",
    "            for i in range(m):\n",
    "                if ring[i] != key[j]:\n",
    "                    dp[i][j] = float('inf')\n",
    "                    continue\n",
    "                dp[i][j]=min(dp[x][j-1] + distance(x, i) + 1 for x in c2i[key[j-1]])\n",
    "        return min(dp[i][n-1] for i in c2i[key[n-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\r\n",
    "        m, n = len(ring), len(key)\r\n",
    "\r\n",
    "        dic = collections.defaultdict(list)\r\n",
    "        for i in range(m):\r\n",
    "            dic[ring[i]].append(i)\r\n",
    "\r\n",
    "        dp = [[float('inf')] * (n + 1) for _ in range(m )]\r\n",
    "        for i in range(m):\r\n",
    "            dp[i][n] = 0\r\n",
    "\r\n",
    "        for j in range(n - 1, -1, -1):\r\n",
    "            for i in range(m):\r\n",
    "                for k in dic[key[j]]:\r\n",
    "                    delta = abs(k - i)\r\n",
    "                    delta = min(delta, m - delta)\r\n",
    "                    dp[i][j] = min(dp[i][j], dp[k][j + 1] + delta + 1)\r\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charToIndex = collections.defaultdict(list)\n",
    "        for idx, c in enumerate(ring):\n",
    "            charToIndex[c].append(idx)\n",
    "        m, n = len(key), len(ring)\n",
    "        dp = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        for k in charToIndex[key[0]]:\n",
    "            dp[0][k] = min(k, n - k) + 1\n",
    "        for i in range(1, m):\n",
    "            for j in charToIndex[key[i - 1]]:\n",
    "                for k in charToIndex[key[i]]:\n",
    "                    delta = abs(j - k)\n",
    "                    delta = min(delta, n - delta)\n",
    "                    dp[i][k] = min(dp[i][k], dp[i - 1][j] + delta + 1)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n = len(ring)\n",
    "        m = len(key)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def solve(p, q):\n",
    "            if q == m:\n",
    "                return 0\n",
    "            ptr1 = p\n",
    "            step1 = 1\n",
    "            while ring[ptr1] != key[q]:\n",
    "                ptr1 = (ptr1 + 1) % n\n",
    "                step1 += 1\n",
    "            ptr2 = p\n",
    "            step2 = 1\n",
    "            while ring[ptr2] != key[q]:\n",
    "                ptr2 = (ptr2 + n - 1) % n\n",
    "                step2 += 1\n",
    "            return min(solve(ptr1, q + 1) + step1, solve(ptr2, q + 1) + step2)\n",
    "        return solve(0, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        ringToInd = defaultdict(list)\n",
    "        n = len(ring)\n",
    "        for i in range(len(ring)):\n",
    "            ringToInd[ring[i]].append(i)\n",
    "        \n",
    "        memo = {}\n",
    "\n",
    "        def dp(i,j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "\n",
    "            character = key[j]\n",
    "            res = float('inf')\n",
    "            \n",
    "            for nxtInd in ringToInd[character]:\n",
    "                ops = 0\n",
    "                # move distance\n",
    "                dist = abs(i - nxtInd)\n",
    "                # clockwise and anticlockwise\n",
    "                dist = min(dist, n-dist)\n",
    "                ops += dist + 1\n",
    "                res = min(res, dp(nxtInd,j+1)+ops)\n",
    "                memo[(i,j)] = res\n",
    "            return res\n",
    "        \n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        # dp[i][j]=n表示当前状态ring[i]拼写key[j:]最少需要的步数n\n",
    "        char_dict = collections.defaultdict(list)\n",
    "        for k, v in enumerate(ring):\n",
    "            char_dict[v].append(k)\n",
    "        m, n = len(ring), len(key)\n",
    "        dp = [[0] * (n + 1) for _ in range(m)]\n",
    "        # base case: dp[i][n]=0\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            for i in range(m):\n",
    "                for idx in char_dict[key[j]]:\n",
    "                    step = min(abs(idx - i), m - abs(idx - i))\n",
    "                    dp_i_j = dp[idx][j + 1] + step + 1\n",
    "                    dp[i][j] = min(dp[i][j], dp_i_j) if dp[i][j] else dp_i_j\n",
    "        print(dp)\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        buc = defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            buc[c].append(i)\n",
    "        n = len(ring)\n",
    "\n",
    "        @cache\n",
    "        def f(idx: int, k: str) -> int:\n",
    "            if len(k) == 0:\n",
    "                return 0\n",
    "            if ring[idx] == k[0]:\n",
    "                return 1 + f(idx, k[1:])\n",
    "            else:\n",
    "                res = 10 ** 9\n",
    "                for i in buc[k[0]]:\n",
    "                    minDis = min((i - idx + n) % n, (idx - i + n) % n)\n",
    "                    res = min(res, 1 + minDis + f(i, k[1:]))\n",
    "                return res\n",
    "\n",
    "        return f(0, key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import lru_cache,cache\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m,n = len(ring), len(key)\n",
    "    \n",
    "        @cache\n",
    "        def f(i:int, j:int):\n",
    "            if j == n:\n",
    "                return 0\n",
    "            if ring[i] == key[j]:\n",
    "                return 1 + f(i, j+1)\n",
    "            res = inf\n",
    "            for k in range(m):\n",
    "                if ring[k] == key[j]:\n",
    "                    step = inf\n",
    "                    if i > k:\n",
    "                        step = min(i - k + 1, k + m - i + 1)\n",
    "                    else:\n",
    "                        step = min(k - i + 1, i + m - k + 1)\n",
    "                    res = min(res, step + f(k, j+1))\n",
    "            return res\n",
    "        \n",
    "        return  f(0,0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        ringList = list(ring)\n",
    "        keyList = list(key)\n",
    "        n = len(ringList)\n",
    "        n_k = len(key)\n",
    "        @cache\n",
    "        def dfs(last_state,index):\n",
    "            res = float('inf')\n",
    "            if index == n_k:\n",
    "                return 0\n",
    "            for i in range(n):\n",
    "                if ringList[i] == key[index]:\n",
    "                    res = min(res, 1+dfs(i,index+1)+min(abs(i-last_state),n-abs(i-last_state)))  \n",
    "            return res \n",
    "        return dfs(0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(index_ring, index_key):\n",
    "            if index_key == len(key):\n",
    "                return 0\n",
    "            \n",
    "            if (index_ring, index_key) in memo:\n",
    "                return memo[(index_ring, index_key)]\n",
    "            \n",
    "            total_steps = float('inf')\n",
    "            for i in range(len(ring)):\n",
    "                if ring[i] == key[index_key]:\n",
    "                    clockwise = abs(i - index_ring)\n",
    "                    anticlockwise = len(ring) - clockwise\n",
    "                    steps = min(clockwise, anticlockwise) + 1 + dfs(i, index_key + 1)\n",
    "                    total_steps = min(total_steps, steps)\n",
    "\n",
    "            memo[(index_ring, index_key)] = total_steps\n",
    "            return total_steps\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import lru_cache,cache\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m,n = len(ring), len(key)\n",
    "        # f(i,j) 表示从ring[i]起步完成key[k] (j <= k < n) 所走的步数\n",
    "        @cache\n",
    "        def f(i:int, j:int):\n",
    "            if j == n:\n",
    "                return 0\n",
    "            # 如果ring[i] == key[j]当前按下button一定是最优解\n",
    "            if ring[i] == key[j]:\n",
    "                return 1 + f(i, j+1)\n",
    "            res = inf\n",
    "            # 下一次无论向左还是向右一定得找到key[j]才行，所以直接在ring中寻找key[j]即可\n",
    "            # 这里其实不用遍历ring字符串，可以用哈希表预处理出key[j]在ring中的下标\n",
    "            for k in range(m):\n",
    "                if ring[k] == key[j]:\n",
    "                    step = inf\n",
    "                    if i > k:\n",
    "                        step = min(i - k + 1, k + m - i + 1)\n",
    "                    else:\n",
    "                        step = min(k - i + 1, i + m - k + 1)\n",
    "                    # step = min(abs(i-k)+1, m+1-abs(i-k))\n",
    "                    res = min(res, step + f(k, j+1))\n",
    "            return res\n",
    "        \n",
    "        return  f(0,0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charToIndex = {}\n",
    "        memo = {}\n",
    "\n",
    "        for i, char in enumerate(ring):\n",
    "            if char not in charToIndex:\n",
    "                charToIndex[char] = []\n",
    "            charToIndex[char].append(i)\n",
    "\n",
    "        def dp(i, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "\n",
    "            n = len(ring)\n",
    "            res = float('inf')\n",
    "\n",
    "            for k in charToIndex[key[j]]:\n",
    "                delta = abs(k - i)\n",
    "                delta = min(delta, n - delta)\n",
    "                nextChar = dp(k, j + 1)\n",
    "                res = min(res, 1 + delta + nextChar)\n",
    "\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n,m = len(ring),len(key)\n",
    "        for i,c in enumerate(ring):\n",
    "            d[c].append(i)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(ps, t):\n",
    "            if t == m:\n",
    "                return m\n",
    "            c = inf\n",
    "            for i in d[key[t]]:\n",
    "                if i >= ps:\n",
    "                    df = min(i-ps, ps+n-i)\n",
    "                else:\n",
    "                    df = min(ps-i, i-ps+n)\n",
    "                c = min(c, df+dfs(i, t+1))\n",
    "            # print(ps,t,c)\n",
    "            return c\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        m,n=len(key),len(ring)\n",
    "        dp=[[float(\"inf\") for _ in range(n)]for _ in range(m)]\n",
    "        def calabs(x,ch):\n",
    "            last=float(\"inf\")\n",
    "            for i in range(n):\n",
    "                if ch==ring[i]:\n",
    "                    last=min(last,abs(x-i),abs(x-i+n),abs(i-x+n))\n",
    "            return last\n",
    "        for i in range(n):\n",
    "            if key[0]==ring[i]:\n",
    "                dp[0][i]=min(i,n-i)\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                ch=ring[j]\n",
    "                if ch!=key[i]:\n",
    "                    continue\n",
    "                for k in range(n):\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][k]+min(abs(j-k),abs(j-k+n),abs(k-j+n)))\n",
    "        print(dp)\n",
    "        return min(dp[-1])+m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\r\n",
    "        pos=[[] for _ in range(26)]\r\n",
    "        orda=ord('a')\r\n",
    "        for i,c in enumerate(ring):\r\n",
    "            pos[ord(c)-orda].append(i)\r\n",
    "        \r\n",
    "        # ret=float('inf')\r\n",
    "        LK=len(key)\r\n",
    "        LR=len(ring)\r\n",
    "        @lru_cache\r\n",
    "        def dfs(idx,cur_pos):\r\n",
    "            nonlocal LK,LR\r\n",
    "            if idx==LK:\r\n",
    "                return 0\r\n",
    "            step=float('inf')\r\n",
    "            for p in pos[ord(key[idx])-orda]:\r\n",
    "                move=min(abs(p-cur_pos),p+LR-cur_pos,cur_pos+LR-p)\r\n",
    "                step=min(step,dfs(idx+1,p)+move+1)\r\n",
    "            return step\r\n",
    "        return dfs(0,0)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        size_ring = len(ring)\n",
    "        size_key = len(key)\n",
    "        cache = dict()\n",
    "        char2index = dict()\n",
    "        for i in range(size_ring):\n",
    "            value = char2index.setdefault(ring[i], [])\n",
    "            value.append(i)\n",
    "        \n",
    "        def traverse(i, j):\n",
    "            if j == size_key:\n",
    "                return 0\n",
    "            \n",
    "            if (i, j) in cache:\n",
    "                return cache[(i, j)]\n",
    "            \n",
    "            min_step = sys.maxsize\n",
    "            for k in char2index[key[j]]:\n",
    "                step = abs(i - k)\n",
    "                step = min(step, size_ring - step) + 1 + traverse(k, j + 1)\n",
    "                min_step = min(min_step, step)\n",
    "            cache[(i, j)] = min_step\n",
    "            return min_step\n",
    "        return traverse(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n, m = len(ring), len(key)\n",
    "        pos = defaultdict(set)\n",
    "        for idx, s in enumerate(ring):\n",
    "            pos[s].add(idx)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int, i: int):\n",
    "            \"\"\"\n",
    "            cur: 当前12点对应ring上的位置\n",
    "            i：想要的字母的指针\n",
    "            \"\"\"\n",
    "            if i == m:\n",
    "                return 0\n",
    "            res = float('inf')\n",
    "            for p in pos[key[i]]:\n",
    "                left = abs(p - cur) + 1 + dfs(p, i + 1)\n",
    "                right = n - abs(p - cur) + 1 + dfs(p, i + 1)\n",
    "                res = min(res, left, right)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for i, ele in enumerate(ring):\n",
    "            dic[ele].append(i)\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if key[j] not in dic:\n",
    "                return -1\n",
    "            res = float(\"inf\")\n",
    "            for ind in dic[key[j]]:\n",
    "                dif = min(abs(i - ind), len(ring) - abs(i - ind))\n",
    "                sub = dp(ind, j + 1)\n",
    "                if sub != -1:\n",
    "                    res = min(res, 1 + dif + sub)\n",
    "            return res if res != float(\"inf\") else -1\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        d = defaultdict(list) # 记录ring中字符对应的索引列表\n",
    "        for i, s in enumerate(ring):\n",
    "            d[s].append(i)\n",
    "        m, n = len(ring), len(key)\n",
    "        # 计算圆盘指针在 ring[i]，输入 key[j..] 的最少指针拨动次数\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == n: return 0\n",
    "            res = inf\n",
    "            for idx in d[key[j]]: # 枚举所有的key[j]的位置\n",
    "                res = min(res,  min(abs(idx - i), m - abs(idx - i)) + dfs(idx, j+1)) # 贪心选择顺时针/逆时针移动次数最少的\n",
    "            return res\n",
    "        return dfs(0, 0) + n   # 按下中心按钮进行拼写，这也将算作 1 步"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        import collections, functools\n",
    "        lookup = collections.defaultdict(list)\n",
    "        for i in range(len(ring)):\n",
    "            lookup[ring[i]].append(i)\n",
    "\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur, k):\n",
    "            if k == len(key):\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            for j in lookup[key[k]]:\n",
    "                res = min(res, min(tmp:= abs(cur - j), len(ring) - tmp) + 1 + dfs(j, k + 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        pos = defaultdict(list[int])\n",
    "        for i, c in enumerate(ring):\n",
    "            pos[c].append(i)\n",
    "        n1, n2 = len(ring), len(key)\n",
    "        @cache\n",
    "        def dfs(p, j):\n",
    "            if j == n2:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for k in pos[key[j]]:\n",
    "                step = min(abs(p - k), abs(n1 - abs(p - k))) + 1\n",
    "                ret = min(ret, dfs(k, j + 1) + step)  \n",
    "            return ret\n",
    "        ans = dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n, m = len(ring), len(key)\n",
    "\n",
    "        char_idxs = defaultdict(set)\n",
    "\n",
    "        for i, c in enumerate(ring):\n",
    "          char_idxs[c].add(i)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(keyIdx, ringIdx):\n",
    "            if keyIdx == m:\n",
    "                return 0\n",
    "\n",
    "            minCount = float('inf')\n",
    "\n",
    "            for idx in char_idxs[key[keyIdx]]:\n",
    "                left = abs(idx - ringIdx) + 1 + dfs(keyIdx + 1, idx)\n",
    "                right = n - abs(idx - ringIdx) + 1 + dfs(keyIdx + 1, idx)\n",
    "\n",
    "                minCount = min(minCount, left, right)\n",
    "\n",
    "            return minCount\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        len_ring = len(ring)\n",
    "        len_key = len(key)\n",
    "        cache = dict()\n",
    "        char2index = dict()\n",
    "        for i in range(len(ring)):\n",
    "            value = char2index.setdefault(ring[i], set())\n",
    "            value.add(i)\n",
    "        \n",
    "        def traverse(ri, ki):\n",
    "            if ki == len_key:\n",
    "                return 0\n",
    "            \n",
    "            cache_key = (ri, ki)\n",
    "            if cache_key in cache:\n",
    "                return cache[cache_key]\n",
    "            \n",
    "            min_step = sys.maxsize\n",
    "            for i in char2index[key[ki]]:\n",
    "                step = abs(ri - i)\n",
    "                step = min(step, len_ring - step) + 1 + traverse(i, ki + 1)\n",
    "                min_step = min(min_step, step)\n",
    "            cache[cache_key] = min_step\n",
    "            return min_step\n",
    "        return traverse(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        ring_len = len(ring)\n",
    "        ring = [ord(c)-97 for c in ring]\n",
    "        key = [ord(c)-97 for c in key]\n",
    "        left = []\n",
    "        prev = [-1] * 26\n",
    "        for i, c in enumerate(ring):\n",
    "            prev[c] = i\n",
    "        for i, c in enumerate(ring):\n",
    "            prev[c] = i\n",
    "            left.append(prev[::])\n",
    "        right = [None] * len(ring)\n",
    "        next = [-1] * 26\n",
    "        for i in range(len(ring)-1, -1, -1):\n",
    "            next[ring[i]] = i\n",
    "        for i in range(len(ring)-1, -1, -1):\n",
    "            next[ring[i]] = i\n",
    "            right[i] = next[::]\n",
    "        d = [[None] * len(ring) for _ in range(len(key))]\n",
    "        d.append([0] * len(ring))\n",
    "        def dfs(ring_index, key_index):\n",
    "            if d[key_index][ring_index] != None: return d[key_index][ring_index]\n",
    "\n",
    "            prev = left[ring_index][key[key_index]]\n",
    "            next = right[ring_index][key[key_index]]\n",
    "            ans = min(dfs(prev, key_index+1) + (ring_index - prev)%ring_len,\n",
    "                      dfs(next, key_index+1) + (next-ring_index)%ring_len) + 1\n",
    "            d[key_index][ring_index] = ans\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        import collections, functools\n",
    "        lookup = collections.defaultdict(list)\n",
    "        for i in range(len(ring)):\n",
    "            lookup[ring[i]].append(i)\n",
    "\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur, k):\n",
    "            if k == len(key):\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            for j in lookup[key[k]]:\n",
    "                res = min(res, min(tmp:= abs(cur - j), len(ring) - tmp) + 1 + dfs(j, k + 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(ring, key, index):\n",
    "            if index >= len(key):\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            # 找到所有能旋转的位置\n",
    "            l_index = ring.find(key[index])\n",
    "\n",
    "            min_val = []\n",
    "            while l_index != -1:\n",
    "                # 如果当前位置在字符串左半边，使用逆时针旋转,右半边使用顺时针，+ 1 是拼写操作\n",
    "                d1 = l_index\n",
    "                d2 = len(ring)-d1\n",
    "                min_val.append(min(d1,d2)+1)\n",
    "                # 获得旋转后的新表盘\n",
    "                new_ring = ring[l_index:] + ring[:l_index]\n",
    "\n",
    "                # 寻找下一个旋转点\n",
    "                min_val[-1] += dfs(new_ring, key, index + 1)\n",
    "                l_index = ring.find(key[index], l_index + 1)\n",
    "\n",
    "            res = res + min(min_val) if min_val else 0\n",
    "            return res\n",
    "\n",
    "        return dfs(ring, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\r\n",
    "        import collections, functools\r\n",
    "        lookup = collections.defaultdict(list)\r\n",
    "        steps = collections.defaultdict(int)\r\n",
    "        # 把所有可以旋转的字符串找出来\r\n",
    "        for i in range(len(ring)):\r\n",
    "            tmp = ring[i:] + ring[:i]\r\n",
    "            # 加入以开头字母为键的数组中\r\n",
    "            lookup[ring[i]].append(tmp)\r\n",
    "            # 距离原始ring顺时针旋转需要几步\r\n",
    "            steps[tmp] = i\r\n",
    "\t\t\r\n",
    "        # 从一个字符串到另一字符串最少旋转的步数\r\n",
    "        def cal_steps(cur, nxt):\r\n",
    "            return min(tmp := abs(steps[cur] - steps[nxt]), len(ring) - tmp)\r\n",
    "        \r\n",
    "        @functools.lru_cache(None)\r\n",
    "        def dfs(cur, k):\r\n",
    "            if k == len(key):\r\n",
    "                return 0\r\n",
    "            res = float(\"inf\")\r\n",
    "            for word in lookup[key[k]]:\r\n",
    "                res = min(res, cal_steps(cur, word) + 1 + dfs(word, k + 1))\r\n",
    "            return res\r\n",
    "\r\n",
    "        return dfs(ring, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        # ring = \"godding\"\n",
    "        # key = \"gd\"\n",
    "\n",
    "        # ring = \"xrrakuulnczywjs\"\n",
    "        # key = \"jrlucwzakzussrlckyjjsuwkuarnaluxnyzcnrxxwruyr\"\n",
    "\n",
    "        con = []\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(s, index, count):\n",
    "            # print(s, key[index])\n",
    "            if index == len(key):\n",
    "                # con.append(count)\n",
    "                return count\n",
    "\n",
    "            if s[0] == key[index]:\n",
    "                tmp_count = 0\n",
    "                tmp_count += 1\n",
    "                return dfs(s, index+1, tmp_count) + count\n",
    "            else:\n",
    "                s1 = s\n",
    "                s2 = s\n",
    "                count1 = 0\n",
    "                count2 = 0\n",
    "                # 逆时针\n",
    "                while True:\n",
    "                    s1 = s1[1:] + s1[0]\n",
    "                    count1 += 1\n",
    "                    if s1[0] == key[index]:\n",
    "                        count1 += 1\n",
    "                        break\n",
    "                res1 = dfs(s1, index+1, count1) + count\n",
    "                # 顺时针\n",
    "                while True:\n",
    "                    s2 = s2[-1] + s2[:-1]\n",
    "                    count2 += 1\n",
    "                    if s2[0] == key[index]:\n",
    "                        count2 += 1\n",
    "                        break\n",
    "                res2 = dfs(s2, index+1, count2) + count\n",
    "                return min(res1, res2)\n",
    "\n",
    "        result = dfs(ring, 0, 0)\n",
    "        print(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(maxsize=len(key))\n",
    "        def dfs(ring, key, index):\n",
    "            if index >= len(key):\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            # 找到所有能旋转的位置\n",
    "            l_index = ring.find(key[index])\n",
    "\n",
    "            min_val = []\n",
    "            while l_index != -1:\n",
    "                # 如果当前位置在字符串左半边，使用逆时针旋转,右半边使用顺时针，+ 1 是拼写操作\n",
    "                d1 = l_index\n",
    "                d2 = len(ring)-d1\n",
    "                min_val.append(min(d1,d2)+1)\n",
    "                # 获得旋转后的新表盘\n",
    "                new_ring = ring[l_index:] + ring[:l_index]\n",
    "\n",
    "                # 寻找下一个旋转点\n",
    "                min_val[-1] += dfs(new_ring, key, index + 1)\n",
    "                l_index = ring.find(key[index], l_index + 1)\n",
    "\n",
    "            res = res + min(min_val) if min_val else 0\n",
    "            return res\n",
    "\n",
    "        return dfs(ring, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        n = len(ring)\n",
    "        m = len(key)\n",
    "        dp_table = [[-1] * (m+1) for _ in range(n+1)]\n",
    "\n",
    "        ring_pos_map = {}\n",
    "        for i in range(len(ring)):\n",
    "            ring_pos_map.setdefault(ring[i], [])\n",
    "            ring_pos_map[ring[i]].append(i)\n",
    "\n",
    "        def dp(s1, s2, p1, p2):\n",
    "            if dp_table[p1][p2] != -1:\n",
    "                return dp_table[p1][p2]\n",
    "            res = -1\n",
    "            if p2 == len(s2):\n",
    "                res = 0\n",
    "            elif s1[p1] == s2[p2]:\n",
    "                res = dp(s1, s2, p1, p2+1) + 1 # 按按钮\n",
    "            else:\n",
    "                res_list = []\n",
    "                for pos in ring_pos_map[s2[p2]]:\n",
    "                    t = min(abs(p1-pos), len(s1)-abs(p1-pos)) + 1  # 转+按\n",
    "                    res_list.append(dp(s1, s2, pos, p2+1)+t)\n",
    "                res =  min(res_list)\n",
    "            dp_table[p1][p2] = res\n",
    "            return res\n",
    "        return dp(ring, key, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        import collections, functools\n",
    "        lookup = collections.defaultdict(list)\n",
    "        steps = collections.defaultdict(int)\n",
    "        # 把所有可以旋转的字符串找出来\n",
    "        for i in range(len(ring)):\n",
    "            tmp = ring[i:] + ring[:i]\n",
    "            # 加入以开头字母为键的数组中\n",
    "            lookup[ring[i]].append(tmp)\n",
    "            # 距离原始ring顺时针旋转需要几步\n",
    "            steps[tmp] = i\n",
    "\t\t\n",
    "        # 从一个字符串到另一字符串最少旋转的步数\n",
    "        def cal_steps(cur, nxt):\n",
    "            return min(tmp := abs(steps[cur] - steps[nxt]), len(ring) - tmp)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur, k):\n",
    "            if k == len(key):\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            for word in lookup[key[k]]:\n",
    "                res = min(res, cal_steps(cur, word) + 1 + dfs(word, k + 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(ring, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(maxsize=len(key))\n",
    "        \n",
    "        def dfs(ring, key, index):\n",
    "            if index >= len(key):\n",
    "                return 0\n",
    "\n",
    "            # 找到第一个旋转的位置\n",
    "            l_index = ring.find(key[index])\n",
    "\n",
    "            min_val = []\n",
    "            while l_index != -1:\n",
    "                # 如果当前位置在字符串左半边，使用逆时针旋转,右半边使用顺时针，+ 1 是拼写操作\n",
    "                d1 = l_index\n",
    "                d2 = len(ring)-d1\n",
    "                min_val.append(min(d1,d2)+1)\n",
    "                # 获得旋转后的新表盘\n",
    "                new_ring = ring[l_index:] + ring[:l_index]\n",
    "\n",
    "                # 寻找下一个旋转点\n",
    "                min_val[-1] += dfs(new_ring, key, index + 1)\n",
    "                l_index = ring.find(key[index], l_index + 1)\n",
    "\n",
    "            return min(min_val) if min_val else 0\n",
    "\n",
    "        return dfs(ring, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(maxsize=len(key))\n",
    "        def dfs(ring, key, index):\n",
    "            if index >= len(key):\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            # 找到第一个旋转的位置\n",
    "            l_index = ring.find(key[index])\n",
    "\n",
    "            min_val = []\n",
    "            while l_index != -1:\n",
    "                # 如果当前位置在字符串左半边，使用逆时针旋转,右半边使用顺时针，+ 1 是拼写操作\n",
    "                d1 = l_index\n",
    "                d2 = len(ring)-d1\n",
    "                min_val.append(min(d1,d2)+1)\n",
    "                # 获得旋转后的新表盘\n",
    "                new_ring = ring[l_index:] + ring[:l_index]\n",
    "\n",
    "                # 寻找下一个旋转点\n",
    "                min_val[-1] += dfs(new_ring, key, index + 1)\n",
    "                l_index = ring.find(key[index], l_index + 1)\n",
    "\n",
    "            res = res + min(min_val) if min_val else 0\n",
    "            return min(min_val) if min_val else 0\n",
    "\n",
    "        return dfs(ring, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        con = []\n",
    "        @lru_cache()\n",
    "        def dfs(s, index, count):\n",
    "            if index == len(key):\n",
    "                return count\n",
    "\n",
    "            if s[0] == key[index]:\n",
    "                tmp_count = 0\n",
    "                tmp_count += 1\n",
    "                return dfs(s, index+1, tmp_count) + count\n",
    "            else:\n",
    "                s1 = s\n",
    "                s2 = s\n",
    "                count1 = 0\n",
    "                count2 = 0\n",
    "                # 逆时针\n",
    "                while True:\n",
    "                    s1 = s1[1:] + s1[0]\n",
    "                    count1 += 1\n",
    "                    if s1[0] == key[index]:\n",
    "                        count1 += 1\n",
    "                        break\n",
    "                res1 = dfs(s1, index+1, count1) + count\n",
    "                # 顺时针\n",
    "                while True:\n",
    "                    s2 = s2[-1] + s2[:-1]\n",
    "                    count2 += 1\n",
    "                    if s2[0] == key[index]:\n",
    "                        count2 += 1\n",
    "                        break\n",
    "                res2 = dfs(s2, index+1, count2) + count\n",
    "                return min(res1, res2)\n",
    "\n",
    "        result = dfs(ring, 0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        # 字符 -> 索引列表\n",
    "        char_id = {}\n",
    "        for i, c in enumerate(ring):\n",
    "            if c not in char_id.keys():\n",
    "                char_id[c] = []\n",
    "            char_id[c].append(i)\n",
    "        memo = [[0] * len(key) for _ in range(len(ring))]\n",
    "\n",
    "        # 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数\n",
    "        def dp(ring, i, key, j):\n",
    "            n = len(ring)\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            res = float('inf')\n",
    "            # ring 上可能有多个字符 key[j]\n",
    "            for k in char_id[key[j]]:\n",
    "                # 拨动指针的次数\n",
    "                delta = abs(i - k)\n",
    "                # 选择顺时针还是逆时针\n",
    "                delta = min(delta, n - delta)\n",
    "                # 将指针拨到 ring[k]，继续输入 key[j+1..]\n",
    "                sub = dp(ring, k, key, j+1)\n",
    "                res = min(res, 1 + delta + sub)\n",
    "            memo[i][j] = res\n",
    "            return memo[i][j]\n",
    "\n",
    "        return dp(ring, 0, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        \n",
    "        def dp(ring, i, key, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            res = float('inf') \n",
    "            for idx in dic[key[j]]:\n",
    "                delta = min(abs(idx - i), len(ring) - abs(idx - i))\n",
    "                res = min(res, 1 + delta  + dp(ring, idx, key, j+1))\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            dic[c].append(i)\n",
    "\n",
    "        m, n = len(ring), len(key)\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        return dp(ring, 0, key, 0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        # def lt514(ring,key):\n",
    "        #     n=len(key)\n",
    "        #     n_ring=len(ring)\n",
    "        #     d=defaultdict(list)\n",
    "        #     for ch in key:\n",
    "        #         if not d[ch]:\n",
    "        #             for i in range(n_ring):\n",
    "        #                 if ring[i]==ch:d[ch].append(i)\n",
    "        #     # print(d)\n",
    "        #     def dfs(ct,key_cur,ring_cur):\n",
    "        #         if key_cur==0 and key[key_cur]!=ring[ring_cur]:\n",
    "        #             temp_=[]\n",
    "        #             for ring_next in d[key[key_cur]]:\n",
    "        #                 step=min(abs(ring_next-ring_cur),n_ring-abs(ring_next-ring_cur))\n",
    "        #                 temp_.append(dfs(step,key_cur,ring_next))\n",
    "        #             return min(temp_)\n",
    "        #         ct+=1\n",
    "        #         if key_cur==n-1:\n",
    "        #             return ct\n",
    "        #         ring_nexts=d[key[key_cur+1]]\n",
    "        #         temp=[]\n",
    "        #         for ring_next in ring_nexts:\n",
    "        #             step=min(abs(ring_next-ring_cur),n_ring-abs(ring_next-ring_cur))\n",
    "        #             temp.append(dfs(ct+step,key_cur+1,ring_next))\n",
    "        #         return min(temp)\n",
    "        #     return dfs(0,0,0)\n",
    "        # return lt514(ring,key)\n",
    "\n",
    "        # def lt514_2(ring,key):\n",
    "        #     key_n = len(key)\n",
    "        #     ring_n = len(ring)\n",
    "        #     d = defaultdict(list)\n",
    "        #     for ch in key:\n",
    "        #         if not d[ch]:\n",
    "        #             for i in range(ring_n):\n",
    "        #                 if ring[i] == ch: d[ch].append(i)\n",
    "        #     chain=[[[0,0,0]]]\n",
    "        #     for key_cur in range(key_n):\n",
    "        #         key_cur_temp=[]\n",
    "        #         for ring_cur in d[key[key_cur]]:\n",
    "        #             temp=[]\n",
    "        #             for key_pre,ring_pre,ct_pre in chain[-1]:\n",
    "        #                 step=min(abs(ring_cur-ring_pre),ring_n-abs(ring_cur-ring_pre))\n",
    "        #                 temp.append(ct_pre+step+1)\n",
    "        #             key_cur_temp.append([key_cur,ring_cur,min(temp)])\n",
    "        #         chain.append(key_cur_temp)\n",
    "        #     return min([e[2] for e in chain[-1]])\n",
    "        # return lt514_2(ring,key)\n",
    "\n",
    "        def lt514_3(ring,key):\n",
    "            key_n = len(key)\n",
    "            ring_n = len(ring)\n",
    "            d = defaultdict(list)\n",
    "            for ch in key:\n",
    "                if not d[ch]:\n",
    "                    for i in range(ring_n):\n",
    "                        if ring[i] == ch: d[ch].append(i)\n",
    "            state=defaultdict(int)\n",
    "            def dfs(key_cur,ring_cur):\n",
    "                if state[(key_cur,ring_cur)]:return state[(key_cur,ring_cur)]\n",
    "                if key_cur==0:\n",
    "                    step=min(ring_cur,ring_n-ring_cur)+1\n",
    "                    state[(key_cur, ring_cur)]=step\n",
    "                    return step\n",
    "                temp=[]\n",
    "                for ring_pre in d[key[key_cur-1]]:\n",
    "                    if not d[(key_cur-1,ring_pre)]:d[(key_cur-1,ring_pre)]=dfs(key_cur-1,ring_pre)\n",
    "                    step=min(abs(ring_cur-ring_pre),ring_n-abs(ring_cur-ring_pre))+1\n",
    "                    temp.append(step+d[(key_cur-1,ring_pre)])\n",
    "                state[(key_cur, ring_cur)]=min(temp)\n",
    "                return state[(key_cur, ring_cur)]\n",
    "            return min([dfs(key_n-1,ring_cur) for ring_cur in d[key[key_n-1]] ])\n",
    "        return lt514_3(ring,key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charIndex = defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            if c not in charIndex:\n",
    "                charIndex[c] = []\n",
    "            charIndex[c].append(i)\n",
    "\n",
    "        memo = [[0] * len(key) for _ in range(len(ring))]\n",
    "        # 当前指向i, 得到key[j:]需要多少操作\n",
    "        def dp(i, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            res = float('inf')\n",
    "            for k in charIndex[key[j]]:\n",
    "                delta = abs(k - i)\n",
    "                delta = min(delta, len(ring) - delta)\n",
    "                subProblem = dp(k, j + 1)\n",
    "                res = min(res, delta + 1 + subProblem)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        return dp(0, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ring, key, index):\n",
    "            if index >= len(key):\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            # 找到所有能旋转的位置\n",
    "            l_index = ring.find(key[index])\n",
    "\n",
    "            min_val = []\n",
    "            while l_index != -1:\n",
    "                # 如果当前位置在字符串左半边，使用逆时针旋转 + 1 是拼写操作\n",
    "                if l_index <= len(ring) // 2:\n",
    "                    min_val.append(l_index + 1)\n",
    "                else:\n",
    "                    # 否则使用顺时针旋转\n",
    "                    min_val.append(len(ring) - l_index + 1)\n",
    "                # 获得旋转后的新表盘\n",
    "                new_ring = ring[l_index:] + ring[:l_index]\n",
    "\n",
    "                # 寻找下一个旋转点\n",
    "                min_val[-1] += dfs(new_ring, key, index + 1)\n",
    "                l_index = ring.find(key[index], l_index + 1)\n",
    "\n",
    "            res = res + min(min_val) if min_val else 0\n",
    "            return res\n",
    "\n",
    "        return dfs(ring, key, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        @cache\n",
    "        def dfs(s,i):\n",
    "            if i == len(key):\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j in range(len(s)):\n",
    "                if s[j] == key[i]:\n",
    "                    ans = min(ans,j + 1 + dfs(s[j:] + s[:j],i + 1))\n",
    "                if s[-j] == key[i]:\n",
    "                    ans = min(ans,j + 1 + dfs(s[-j:] + s[:-j],i + 1))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(ring,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\r\n",
    "        def dp(i , j, ring, key):\r\n",
    "            if j == len(key):\r\n",
    "                return 0\r\n",
    "\r\n",
    "            if memo[i][j]:\r\n",
    "                return memo[i][j]\r\n",
    "\r\n",
    "            indexkey = []\r\n",
    "            for index, c in enumerate(ring):\r\n",
    "                if c == key[j]:\r\n",
    "                    indexkey.append(index)\r\n",
    "            \r\n",
    "            res = float('inf')\r\n",
    "            for index in indexkey:\r\n",
    "                delta = abs(index - i)\r\n",
    "                delta = min(delta, len(ring) - delta)\r\n",
    "\r\n",
    "                res = min(res, 1 + delta + dp(index, j + 1, ring, key))\r\n",
    "            memo[i][j] = res\r\n",
    "\r\n",
    "            return res\r\n",
    "\r\n",
    "        memo = [[0] * len(key) for _ in range(len(ring))]\r\n",
    "\r\n",
    "        return dp(0, 0, ring, key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charToIndex = defaultdict(list)\n",
    "        memo = [[0] * len(key) for _ in range(len(ring))]\n",
    "        for i, c in enumerate(ring):\n",
    "            charToIndex[c].append(i)\n",
    "        \n",
    "        def dp(i, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            res = float('inf')\n",
    "            for k in charToIndex[key[j]]:\n",
    "                delta = abs(i - k)\n",
    "                delta = min(delta, len(ring) - delta)\n",
    "                sub_problem = dp(k, j+1)\n",
    "                res = min(res, sub_problem + delta + 1)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        return self.solution(ring,key)\n",
    "    def solution(self,ring:str,key:str) -> int:\n",
    "        memo = [[0 for _ in range(len(key))] for _ in range(len(ring))]\n",
    "        appear = {}\n",
    "        # 记录所有字符出现的位置,一个字符可能在多个位置均有出现\n",
    "        for i,c in enumerate(ring):\n",
    "        \tif c not in appear:\n",
    "        \t\tappear[c] = []\n",
    "        \tappear[c].append(i)\n",
    "        def minOpNum(i:int,j:int) -> int:\n",
    "        \tif j == len(key):\n",
    "        \t\treturn 0\n",
    "        \tif memo[i][j] != 0:\n",
    "        \t\treturn memo[i][j]\n",
    "        \tres = float('inf')\n",
    "        \tfor k in appear[key[j]]:\n",
    "        \t\tdelta = abs(i-k)\n",
    "        \t\tdelta = min(delta,len(ring)-delta) # 对应顺时针和逆时针转动\n",
    "        \t\tsub = minOpNum(k,j+1) # 拨到某个指针后,凑出剩下的k[j...]需要的最少操作数\n",
    "        \t\tres = min(res,1+delta+sub) # +1是因为要按一下'button'\n",
    "        \tmemo[i][j] = res\n",
    "        \treturn memo[i][j]\n",
    "        return minOpNum(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        # 圆盘固定，我们可以拨动指针；现在需要我们拨动指针并按下按钮，以最少的操作次数输入key对应的字符串\n",
    "        # 动态规划\n",
    "        # 「状态」就是i和j两个变量。我们可以用i表示当前圆盘上指针指向的字符（也就是ring[i]）；用j表示需要输入的字符（也就是key[j]）\n",
    "        # 当圆盘指针指向ring[i]时，输入字符串key[j..]至少需要dp(ring, i, key, j)次操作\n",
    "        # 「选择」就是「如何拨动指针得到待输入的字符」。\n",
    "\n",
    "        m, n = len(ring), len(key)\n",
    "        memo = [[0] * n for _ in range(m)]\n",
    "\n",
    "        # 记录圆环上字符到索引的映射(因为圆盘存在同一个字符有多个的可能)\n",
    "        charToIndex = {}\n",
    "        for i in range(m):\n",
    "            if ring[i] not in charToIndex.keys():\n",
    "                charToIndex[ring[i]] = [i]\n",
    "            else:\n",
    "                charToIndex[ring[i]].append(i)\n",
    "\n",
    "        # 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数\n",
    "        def dp(ring, i, key, j):\n",
    "            # base case, key遍历完了\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "\n",
    "            # 查看备忘录\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "\n",
    "            n = len(ring)\n",
    "            res = float(\"INF\")\n",
    "            # ring上可能有多个字符，需要看看波动到哪个字符效果更好\n",
    "            for k in charToIndex[key[j]]:\n",
    "                # 拨动指针的次数\n",
    "                delta = abs(k-i)\n",
    "                # 看顺时针/逆时针那个短\n",
    "                delta = min(delta, n-delta)\n",
    "                # 将指针拨到 ring[k]，继续输入 key[j+1..]\n",
    "                subproblem = dp(ring, k, key, j+1)\n",
    "                # 选择「整体」操作次数最少的(即选滑到那个字符的最少次数)\n",
    "                res = min(res, 1+delta+subproblem) # 1是按钮\n",
    "\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "\n",
    "        return dp(ring, 0, key, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "\n",
    "        #dp[i][j]表示指针指向ring第i个字母时，转出key[j:]所需要的最少步数。\n",
    "        #需要求解dp[0][0]，base case:dp[k][len(key)] = 0\n",
    "\n",
    "        def dp(i, j):\n",
    "            if j == n:\n",
    "                return 0\n",
    "            if memo[i][j] != float('inf'):\n",
    "                return memo[i][j]\n",
    "            \n",
    "            for idx in imap[key[j]]:\n",
    "                dis = abs(i - idx)\n",
    "                dis = min(dis, m-dis)\n",
    "                sub_problem = dp(idx, j+1)\n",
    "                memo[i][j] = min(memo[i][j], 1+dis+sub_problem)       \n",
    "            \n",
    "            return memo[i][j]\n",
    "\n",
    "        m = len(ring)\n",
    "        n = len(key)\n",
    "        memo = [[float('inf')]*(n+1) for _ in range(m)]\n",
    "        imap = collections.defaultdict(list)\n",
    "        for index, val in enumerate(ring):\n",
    "            imap[val].append(index)\n",
    "        return dp(0,0)\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRotateSteps(self, ring: str, key: str) -> int:\n",
    "        charIndex = defaultdict(list)\n",
    "        for i, c in enumerate(ring):\n",
    "            if c not in charIndex:\n",
    "                charIndex[c] = []\n",
    "            charIndex[c].append(i)\n",
    "\n",
    "        memo = [[0] * len(key) for _ in range(len(ring))]\n",
    "        # 当前指向i, 得到key[j:]需要多少操作\n",
    "        def dp(ring, i, key, j):\n",
    "            if j == len(key):\n",
    "                return 0\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            res = float('inf')\n",
    "            for k in charIndex[key[j]]:\n",
    "                delta = abs(k - i)\n",
    "                delta = min(delta, len(ring) - delta)\n",
    "                subProblem = dp(ring, k, key, j + 1)\n",
    "                res = min(res, delta + 1 + subProblem)\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "        return dp(ring, 0, key, 0)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
